{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 线性模型\n",
    "&emsp;&emsp;笔记的前一部分主要是对机器学习预备知识的概括，包括机器学习的定义/术语、学习器性能的评估/度量以及比较，本篇之后将主要对具体的学习算法进行理解总结，本篇则主要是第3章的内容——线性模型。  \n",
    "&emsp;&emsp;谈及线性模型，其实我们很早就已经与它打过交道，还记得高中数学必修3课本中那个顽皮的“最小二乘法”吗？这就是线性模型的经典算法之一：根据给定的$(x,y)$点对，求出一条与这些点拟合效果最好的直线$y=ax+b$，之前我们利用下面的公式便可以计算出拟合直线的系数$a,b$（3.1中给出了具体的计算过程），从而对于一个新的$x$，可以预测它所对应的$y$值。前面我们提到：在机器学习的术语中，当预测值为连续值时，称为“回归问题”，离散值时为“分类问题”。本篇先从线性回归任务开始，接着讨论分类和多分类问题。\n",
    "$$\n",
    "b=\\frac{x_1 y_1+x_2 y_2+\\cdots+x_n y_n-n \\overline{x} \\overline{y}}{x_1^2+x_2^2+\\cdots+x_n^2 -n \\overline{x}^2} ; a=\\overline{y}-b \\overline{x}\n",
    "$$\n",
    "\n",
    "### 线性回归\n",
    "&emsp;&emsp;线性回归问题就是试图学到一个线性模型尽可能准确地预测新样本的输出值，例如：通过历年的人口数据预测2017年人口数量。在这类问题中，往往我们会先得到一系列的有标记数据，例如：2000-->13亿...2016-->15亿，这时输入的属性只有一个，即年份；也有输入多属性的情形，假设我们预测一个人的收入，这时输入的属性值就不止一个了，例如：（学历，年龄，性别，颜值，身高，体重）-->15k。  \n",
    "&emsp;&emsp;有时这些输入的属性值并不能直接被我们的学习模型所用，需要进行相应的处理，对于连续值的属性，一般都可以被学习器所用，有时会根据具体的情形作相应的预处理，例如：归一化等；对于离散值的属性，可作下面的处理：\n",
    "\n",
    "- 若属性值之间存在“序关系”，则可以将其转化为连续值，例如：身高属性分为“高”“中等”“矮”，可转化为数值：$\\{1，0.5，0\\}$。\n",
    "- 若属性值之间不存在“序关系”，则通常将其转化为向量的形式，例如：性别属性分为“男”“女”，可转化为二维向量：$\\{(1，0)，(0，1)\\}$。\n",
    "\n",
    "（1）当输入属性只有一个的时候，就是最简单的情形，也就是我们高中时最熟悉的“最小二乘法”（Euclidean Distance），首先计算出每个样本预测值与真实值之间的误差并求和，通过最小化均方误差MSE，使用求偏导等于零的方法计算出拟合直线$y=wx+b$的两个参数$w$和$b$，计算过程如下：\n",
    "$$\n",
    "\\begin{aligned}(w^*, b^*) &=\\underset{(w, b)}{\\arg \\min } \\sum_{i=1}^{m}\\left(f(x_{i})-y_{i}\\right)^2 \\\\ \n",
    "&=\\underset{(w, b)}{\\arg \\min } \\sum_{i=1}^m(y_i-w x_i-b)^2 \\end{aligned} \\\\\n",
    "E_{(w, b)}=\\sum_{i=1}^{m}(y_{i}-w x_{i}-b)^2 \\\\\n",
    "\\frac{\\partial E_{(w, b)}}{\\partial w} =2\\left(w \\sum_{i=1}^m x_i^2-\\sum_{i=1}^m (y_i-b) x_{i}\\right) = 0 \\\\ \n",
    "\\frac{\\partial E_{(w, b)}}{\\partial b} =2\\left(m b-\\sum_{i=1}^m (y_i-w x_i) \\right) = 0 \\\\\n",
    " w=\\frac{\\displaystyle \\sum_{i=1}^m y_i(x_i-\\overline{x})}{ \\displaystyle \\sum_{i=1}^m x_i^2-\\frac{1}{m}(\\sum_{i=1}^{m} x_{i})^{2}} \\\\\n",
    "b=\\frac{1}{m} \\sum_{i=1}^m (y_i-w x_i)\n",
    "$$\n",
    "$\\displaystyle b=\\frac{1}{m} \\sum_{i=1}^m (y_i-w x_i)$是经过样本的均值点。  \n",
    "（2）当输入属性有多个的时候，例如对于一个样本有$d$个属性$\\{(x_1,x_2,\\cdots,x_d),y\\}$，则$y=wx+b$需要写成：$$y_i=w_1x_{i1}+w_2x_{i2}+ \\cdots + w_dx_{id} + b$$&emsp;&emsp;通常对于多元问题，常常使用矩阵的形式来表示数据。在本问题中，将具有$m$个样本的数据集表示成矩阵$X$，将系数$w$与$b$合并成一个列向量，这样每个样本的预测值以及所有样本的均方误差最小化就可以写成下面的形式：\n",
    "$$\n",
    "\\hat{w}=(w ; b)=\\left(\\begin{array}{c}w_1 \\\\ w_2 \\\\ {\\cdots} \\\\ w_d \\\\ b \\end{array}\\right) \\\\\n",
    "X=\\left(\\begin{array}{ccccc} \n",
    "x_{11} & x_{12} & \\dots & x_{1d} & 1 \\\\ \n",
    "x_{21} & x_{22} & \\dots & x_{2d} & 1 \\\\ \n",
    "\\vdots & \\vdots & \\ddots & \\vdots & \\vdots \\\\ \n",
    "x_{m1} & x_{m2} & \\dots & x_{md} & 1 \n",
    "\\end{array} \\right)=\n",
    "\\left(\\begin{array}{cc} \n",
    "x_1^T & 1 \\\\ \n",
    "x_2^T & 1 \\\\ \n",
    "\\vdots & \\vdots \\\\ \n",
    "x_m^T & 1 \n",
    "\\end{array}\\right) \\\\\n",
    "X^{*} \\hat{w}=\\left(\\begin{array}{ccccc} \n",
    "x_{11} & x_{12} & \\dots & x_{1d} & 1 \\\\ \n",
    "x_{21} & x_{22} & \\dots & x_{2d} & 1 \\\\ \n",
    "\\dots & \\dots & \\dots & \\dots & \\dots \\\\ \n",
    "x_{m1} & x_{m2} & \\dots & x_{md} & 1 \n",
    "\\end{array}\\right) * \n",
    "\\left(\\begin{array}{c} w_1 \\\\ w_2 \\\\ \\dots \\\\ w_d \\\\ b \\end{array}\\right) = \n",
    "\\left(\\begin{array}{c}\n",
    "w_1 x_{11} + w_2 x_{12} + \\ldots + w_d x_{1d} + b \\\\ \n",
    "w_1 x_{21} + w_2 x_{22} + \\ldots + w_d x_{2d} + b \\\\ \n",
    "\\cdots \\\\ \n",
    "w_1 x_{m1} + w_2 x_{m2} + \\ldots + w_d x_{md} + b \n",
    "\\end{array}\\right)=\\left(\\begin{array}{c}\n",
    "f(x_1) \\\\ f(x_2) \\\\ \\dots \\\\ f(x_m) \\end{array}\\right) \\\\\n",
    "\\hat{w}^*=\\underset{\\hat{w}}{\\arg \\min }(y-X \\hat{w})^{T}(y-X \\hat{w})\n",
    "$$&emsp;&emsp;同样地，我们使用最小二乘法对$w$和$b$进行估计，令均方误差的求导等于0，需要注意的是，当一个矩阵的行列式不等于0时，我们才可能对其求逆，因此对于下式，我们需要考虑矩阵（$X^T X$）的行列式是否为0，若不为0，则可以求出其解，若为0，则需要使用其它的方法进行计算，书中提到了引入正则化，此处不进行深入。\n",
    "令$E_{\\hat{w}}=(y-X\\hat{w})^T (y-X\\hat{w})$，对$\\hat{w}$求导可得：  \n",
    "$\\displaystyle \\therefore \\frac{\\partial E_{\\hat{w}}}{\\partial \\hat{w}}=2 X^T(X \\hat{w}-y) = 0$  \n",
    "$\\therefore \\hat{w}^*=(X^T X )^{-1} X^T y, f(\\hat{x}_i)=\\hat{x}_i^T(X^T X)^{-1} X^T y$  \n",
    "&emsp;&emsp;另一方面，有时像上面这种原始的线性回归可能并不能满足需求，例如：$y$值并不是线性变化，而是在指数尺度上变化。这时我们可以采用线性模型来逼近y的衍生物，例如$\\ln y$，这时衍生的线性模型如下所示，实际上就是相当于将指数曲线投影在一条直线上，如下图所示：\n",
    "$\\ln y=w^T x + b$，实际上是广义线性模型的一种特殊情况：$g(y)=\\ln(y)$\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/3-1-Log-Linear-Regression.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图3-1 对数线性回归示意图</div></center>\n",
    "\n",
    "&emsp;&emsp;更一般地，考虑所有$y$的衍生情形，就得到了“广义的线性模型”（generalized linear model），其中，$g(\\cdot)$称为联系函数（link function）。\n",
    "$$y=g^{-1}(w^T x + b)$$\n",
    "\n",
    "### 线性几率回归\n",
    "&emsp;&emsp;回归就是通过输入的属性值得到一个预测值，利用上述广义线性模型的特征，是否可以通过一个联系函数，将预测值转化为离散值从而进行分类呢？线性几率回归正是研究这样的问题。对数几率引入了一个对数几率函数（logistic function），将预测值投影到0-1之间，从而将线性回归问题转化为二分类问题。\n",
    "$\\displaystyle y=\\frac{1}{1+e^{-z}}$\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/3-2-Unit-Step-Function-and-Logistic-Function.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图3-2 单位阶跃函数与对数几率函数</div></center>\n",
    "\n",
    "$$y=\\frac{1}{1+e^{-(w^T x+b)}} \\longrightarrow \\ln \\frac{y}{1-y}=w^T x + b$$\n",
    "&emsp;&emsp;若将$y$看做样本为正例的概率，$(1-y)$看做样本为反例的概率，则上式实际上使用线性回归模型的预测结果器逼近真实标记的对数几率。因此这个模型称为“对数几率回归”（logistic regression），也有一些书籍称之为“逻辑回归”。下面使用最大似然估计的方法来计算出$w$和$b$两个参数的取值，下面只列出求解的思路，不列出具体的计算过程。\n",
    "$\\displaystyle \\ln \\frac{p(y=1 | x)}{p(y=0 | x)}=w^T x + b $  \n",
    "$\\because p(y=1|x)=1-p(y=0|x)$  \n",
    "正例：$\\displaystyle p(y=1|x) = \\frac{e^{w^T x + b}}{1 + e^{w^T x + b}}$  \n",
    "负例：$\\displaystyle p(y=0|x) = \\frac{1}{1 + e^{w^T x + b}}$  \n",
    "似然函数：$\\displaystyle \\ell(w, b)=\\sum_{i=1}^m \\ln p(y_i | x_i ; w, b)$，对数变乘为加，即所有样本出现真实值的概率乘积最大。\n",
    "\n",
    "### 线性判别分析\n",
    "&emsp;&emsp;线性判别分析（Linear Discriminant Analysis，简称LDA），其基本思想是：将训练样本投影到一条直线上，使得同类的样例尽可能近，不同类的样例尽可能远。如图所示：\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/3-3-LDA.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图3-3 LDA的二维示意图\"+\"、 \"-\"分别代表正例和反例，椭圆表示数据簇的外轮廓，虚线表示投影，红色实心圆和实心三角形分别表示两类样本投影后的中心点</div></center>\n",
    "\n",
    "&emsp;&emsp;给定数据集$D=\\{(x_i,y_i)\\}_{i=1}^m, y_i \\in \\{0,1\\}$，令$X_i,\\mu_i, \\Sigma_i$分别表示第$i \\in \\{0,1\\}$类示例的集合、均值向量、协方差矩阵。若将数据投影到直线$w$上，则两类样本的中心在直线上的投影分别为$w^T \\mu_0$和$w^T \\mu_1$；若将所有样本点都投影到直线上，则两类样本的协方差分别为$w^T \\Sigma_0 w$和$w^T \\Sigma_1 w$。由于直线是一维空间，因此$w^T \\mu_0, w^T \\mu_1, w^T \\Sigma_0 w, w^T \\Sigma_1 w$均为实数。  \n",
    "&emsp;&emsp;想让同类样本点的投影点尽可能接近，不同类样本点投影之间尽可能远，即：让各类的协方差之和尽可能小，不用类之间中心的距离尽可能大。基于这样的考虑，LDA定义了两个散度矩阵。\n",
    "\n",
    "- 类内散度矩阵（within-class scatter matrix）：该值越小越好\n",
    "$$\n",
    "\\begin{aligned} S_w &=\\Sigma_0+\\Sigma_1 \\\\ \n",
    "&=\\sum_{x \\in X_0} (x-\\mu_0) (x-\\mu_0)^T+ \\sum_{x \\in X_1}(x-\\mu_1)(x-\\mu_1)^T \\end{aligned}\n",
    "$$\n",
    "- 类间散度矩阵(between-class scaltter matrix)：该值越大越好\n",
    "$$S_b=(\\mu_0-\\mu_1)(\\mu_0-\\mu_1)^T$$\n",
    "\n",
    "&emsp;&emsp;因此得到了LDA的最大化目标：“广义瑞利商”（generalized Rayleigh quotient）:该值越大越好。\n",
    "$$J=\\frac{w^T S_b w}{w^T S_w w}$$\n",
    "&emsp;&emsp;从而分类问题转化为最优化求解$w$的问题，当求解出$w$后，对新的样本进行分类时，只需将该样本点投影到这条直线上，根据与各个类别的中心值进行比较，从而判定出新样本与哪个类别距离最近。求解$w$的方法如下所示，使用的方法为$\\lambda$乘子。\n",
    "$$\n",
    "\\begin{array}{cl} \n",
    "\\min _{w} & {w^T S_b w} \\\\ \n",
    "{\\text { s.t. }} & {w^T S_w w=1}\\end{array}\n",
    "$$解只与方向有关，而与长度无关。  \n",
    "$\\therefore S_b w = \\lambda S_w w$  \n",
    "$\\therefore S_b w = \\lambda (\\mu_0 - \\mu_1), w=S_w^{-1}(\\mu_0 - \\mu_1)$  \n",
    "&emsp;&emsp;若将$w$看做一个投影矩阵，类似PCA的思想，则LDA可将样本投影到$N-1$维空间（$N$为类簇数），投影的过程使用了类别信息（标记信息），因此LDA也常被视为一种经典的监督降维技术。\n",
    "\n",
    "### 多分类学习\n",
    "&emsp;&emsp;现实中我们经常遇到不只两个类别的分类问题，即多分类问题，在这种情形下，我们常常运用“拆分”的策略，通过多个二分类学习器来解决多分类问题，即将多分类问题拆解为多个二分类问题，训练出多个二分类学习器，最后将多个分类结果进行集成得出结论。最为经典的拆分策略有三种：“一对一”（OvO）、“一对其余”（OvR）和“多对多”（MvM），核心思想与示意图如下所示。\n",
    "\n",
    "- OvO：给定数据集$D$，假定其中有$N$个真实类别，将这$N$个类别进行两两配对（一个正类/一个反类），从而产生$N(N-1)/2$个二分类学习器，在测试阶段，将新样本放入所有的二分类学习器中测试，得出$N(N-1)$个结果，最终通过投票产生最终的分类结果。\n",
    "- OvM：给定数据集$D$，假定其中有$N$个真实类别，每次取出一个类作为正类，剩余的所有类别作为一个新的反类，从而产生$N$个二分类学习器，在测试阶段，得出$N$个结果，若仅有一个学习器预测为正类，则对应的类标作为最终分类结果。\n",
    "- MvM：给定数据集$D$，假定其中有$N$个真实类别，每次取若干个类作为正类，若干个类作为反类（通过ECOC码给出，编码），若进行了$M$次划分，则生成了$M$个二分类学习器，在测试阶段（解码），得出$M$个结果组成一个新的码，最终通过计算海明/欧式距离选择距离最小的类别作为最终分类结果。\n",
    "\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/3-4-OvO-and-OvR.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图3-4 OvO与OvR示意图</div></center>\n",
    "\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/3-5-ECOC-Coding.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图3-5 ECOC编码示意图。\"+1\"、\"-1\"分别表示学习器 $f_i$将该类样本作为正、反例;三元码中\"0\"表示$f_i$不使用该类样本</div></center>\n",
    "\n",
    "### 类别不平衡问题\n",
    "&emsp;&emsp;类别不平衡（class-imbanlance）就是指分类问题中不同类别的训练样本相差悬殊的情况，例如正例有900个，而反例只有100个，这个时候我们就需要进行相应的处理来平衡这个问题。常见的做法有三种：  \n",
    "1. 在训练样本较多的类别中进行“欠采样”（undersampling），比如从正例中采出100个，常见的算法有：EasyEnsemble。\n",
    "2. 在训练样本较少的类别中进行“过采样”（oversampling），例如通过对反例中的数据进行插值，来产生额外的反例，常见的算法有SMOTE。\n",
    "3. 直接基于原数据集进行学习，对预测值进行“再缩放”处理。其中再缩放也是代价敏感学习的基础。\n",
    "$$\\frac{y'}{1-y'}=\\frac{y}{1-y} \\times \\frac{m^{-}}{m^{+}} \\rightarrow \\frac{\\text{cost} (+>-)}{\\text{cost} (->+)}\\quad即代价敏感$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
